翻訳と辞書 Words near each other ・ GRAph ALigner (GRAAL) ・ Graph amalgamation ・ Graph automorphism ・ Graph bandwidth ・ Graph C*-algebra ・ Graph canonization ・ Graph center ・ Graph coloring ・ Graph coloring game ・ Graph continuous function ・ Graph cut ・ Graph cuts in computer vision ・ Graph database ・ Graph drawing ・ Graph dynamical system ・ Graph embedding ・ Graph energy ・ Graph enumeration ・ Graph equation ・ Graph factorization ・ Graph homomorphism ・ Graph isomorphism ・ Graph isomorphism problem ・ Graph kernel ・ Graph labeling ・ Graph literacy ・ Graph manifold ・ Graph minor ・ Graph Modelling Language ・ Graph Nobel Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Graph embedding ： ウィキペディア英語版 Graph embedding In topological graph theory, an embedding (also spelled imbedding) of a graph $G$ on a surface Σ is a representation of $G$ on Σ in which points of Σ are associated to vertices and simple arcs (homeomorphic images of ()) are associated to edges in such a way that: * the endpoints of the arc associated to an edge $e$ are the points associated to the end vertices of $e$, * no arcs include points associated with other vertices, * two arcs never intersect at a point which is interior to either of the arcs. Here a surface is a compact, connected 2-manifold. Informally, an embedding of a graph into a surface is a drawing of the graph on the surface in such a way that its edges may intersect only at their endpoints. It is well known that any graph can be embedded in 3-dimensional Euclidean space $\backslash mathbb^3$〔.〕 and planar graphs can be embedded in 2-dimensional Euclidean space $\backslash mathbb^2$. Often, an embedding is regarded as an equivalence class (under homeomorphisms of Σ) of representations of the kind just described. Some authors define a weaker version of the definition of "graph embedding" by omitting the non-intersection condition for edges. In such contexts the stricter definition is described as "non-crossing graph embedding".〔.〕 This article deals only with the strict definition of graph embedding. The weaker definition is discussed in the articles "graph drawing" and "crossing number". ==Terminology== If a graph $G$ is embedded on a closed surface Σ, the complement of the union of the points and arcs associated to the vertices and edges of $G$ is a family of regions (or faces).〔.〕 A 2-cell embedding or map is an embedding in which every face is homeomorphic to an open disk.〔.〕 A closed 2-cell embedding is an embedding in which the closure of every face is homeomorphic to a closed disk. The genus of a graph is the minimal integer ''n'' such that the graph can be embedded in a surface of genus ''n''. In particular, a planar graph has genus 0, because it can be drawn on a sphere without self-crossing. The non-orientable genus of a graph is the minimal integer ''n'' such that the graph can be embedded in a non-orientable surface of (non-orientable) genus ''n''.〔 The Euler genus of a graph is the minimal integer ''n'' such that the graph can be embedded in an orientable surface of (orientable) genus ''n/2'' or in a non-orientable surface of (non-orientable) genus ''n''. A graph is orientably simple if its Euler genus is smaller than its non-orientable genus. The maximum genus of a graph is the maximal integer ''n'' such that the graph can be 2-cell embedded in an orientable surface of genus ''n''. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Graph embedding」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.